'''
Created on Jan 16, 2011

@author: roni
'''
'''

Created on May 12, 2010

@author: roni
'''
import groupUtils
import logging
from ns2Scenario import Ns2Scenario
from gde import GDE

class Conflict(object):
    def __init__(self,normal_nodes, abnormal_nodes):       
        self.normal_nodes=normal_nodes
        self.abnormal_nodes = abnormal_nodes


    def __str__(self):
        str = '{~Ab('
        for node in self.normal_nodes:
            str = str + "%s," % node
        str = str + '), Ab('
        for node in self.abnormal_nodes:
            str = str + "%s," % node        
        str = str+")}"
        return str
        
class Sherlock(GDE):
    '''
    MBD algorithm for finding the delayed links
    '''
    def __init__(self,activate_prunning = True):
        GDE.__init__(self,activate_prunning)
        if activate_prunning==True:        
            self.name = "Sherlock+"
        else:
            self.name = "Sherlock"
        self.max_diagnoses = float('inf')
    
    def run(self,scenario, observed_details,delay_steps=Ns2Scenario.LINK_DELAY):
        ''' Run the diagnosis 
        param - scenario - a Ns2Scenario object described the model
        param - observed - a map of agent to delay, describing the actual delay seen'''
        self.min_cardinality = float('inf')
        self.expanded = 0
        GDE.run(self,scenario,observed_details,delay_steps)
    
    
    def diagnose(self,conflict_agents, possible_abnormal_nodes, abnormal_nodes = set()):
        ''' Returns a generator function that generates diagnosises 
        param conflict_agents - agents that still have an unexplained conflict 
        param possible_abnormal_nodes - nodes that may be abnormal, which may explain conflict of agents
        param abnormal_nodes - nodes that are assumed to be abnormals (satisfied previous agents)'''
        
        # Generate minimal conflicts       
        logging.info("Searching for conflicts...")
        conflicts = []        
        for agent in conflict_agents:
            nodes_on_path = self.agent_to_nodes_on_path[agent]
            unexplained_delay = self.unexplained[agent]
            possible_abs = nodes_on_path.intersection(possible_abnormal_nodes)
            
            # Conflicts from too much abnormals
            abs_list = groupUtils.all_subsets_of_size(1+unexplained_delay/2, possible_abs)
            for abs in abs_list:
                conflicts.append(Conflict(abs,[]))
            # Conflicts from too much normals
            normals_list = groupUtils.all_subsets_of_size(len(possible_abs)-unexplained_delay/2+1, possible_abs)
            for normals in normals_list:
                conflicts.append(Conflict([],normals))
                
        logging.info("Found %d conflicts" % len(conflicts))
                        
        # Maximal size of search tree
#        search_size = 1
#        for conflict in conflicts:
#            search_size=search_size * (len(conflict.normal_nodes) + len(conflict.abnormal_nodes))
#        logging.info("Max hitting set search tree size %d" % search_size)
        
                        
        # Find hitting set
        logging.info("Search hitting sets...")
        self.find_hitting_sets(conflicts,[],[])
        logging.info("Found %d diagnoses" % len(self.diagnosises))
        
               
        
    
    def find_hitting_sets(self,conflicts,abnormal_nodes = [], normal_nodes = []):
        '''
        Find the hitting set
        '''
        self.expanded = self.expanded+1

        # If finished an hitting set - store diagnosis
        if len(conflicts)==0:
            self.diagnosises.append(list(abnormal_nodes))
            return      
        
        # Check all items in conflicts
        conflict = conflicts.pop()        

        for node in conflict.normal_nodes:
            if node not in abnormal_nodes:
                if node in normal_nodes:
                    self.find_hitting_sets(conflicts,abnormal_nodes,normal_nodes)
                else:
                    normal_nodes.append(node)
                    self.find_hitting_sets(conflicts,abnormal_nodes,normal_nodes)
                    normal_nodes.remove(node)
        
        for node in conflict.abnormal_nodes:
            # Only nodes that are not normal can be set for the hitting set
            if node not in normal_nodes:
                if node in abnormal_nodes:
                    self.find_hitting_sets(conflicts, abnormal_nodes, normal_nodes)
                else:
                    abnormal_nodes.append(node)
                    self.find_hitting_sets(conflicts, abnormal_nodes, normal_nodes)
                    abnormal_nodes.remove(node)
        
        # Return the dealt conflict to enable backtracking
        conflicts.append(conflict)
                     
   
        
        
